package a09_贪心算法;

/**
 * 贪心在哪里？
 * 连续和为负数+下一个数  还不如从下一个数开始
 * 只要连续和不是负数，他都能让后面的数增大
 *
 * 局部最优？
 * 当和为负数，立即抛弃，立刻选择下一个数最为新的起点
 *
 * @author flyduck
 * @since 2025/1/8
 */
public class a04_最大子序和 {
    public static void main(String[] args) {
        int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        a04_最大子序和 test = new a04_最大子序和();
        System.out.println(test.maxSubArray(nums));
    }
    //-2,1,-3,4,-1,2,1,-5,4
    //
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int sum = 0;
        int idx = 0;
        while (idx < nums.length) {
            sum = sum + nums[idx];
            maxSum = Math.max(sum, maxSum);
            if(sum < 0){
                idx = idx + 1;
                sum = 0;
            }else {
                idx++;
            }
        }
        return maxSum;
    }
}
